from typing import *


# 3175 ms 击败 5.82%
class MagicDictionary:

    def __init__(self):
        self.s = set()

    def buildDict(self, dictionary: List[str]) -> None:
        for d in dictionary:
            da = list(d)
            for i in range(len(da)):
                for j in range(1, 27):
                    da[i] = chr((ord(da[i]) - ord("a") + 1) % 26 + ord("a"))
                    if j < 26:
                        self.s.add("".join(da))

    def search(self, searchWord: str) -> bool:
        return searchWord in self.s


# 287 ms 击败 14.56%
class MagicDictionary:

    def __init__(self):
        self.s = set()
        self.d = Counter()

    def buildDict(self, dictionary: List[str]) -> None:
        for d in dictionary:
            self.s.add(d)
            da = list(d)
            for i in range(len(da)):
                c = da[i]
                da[i] = "*"
                self.d["".join(da)] += 1
                da[i] = c

    def search(self, searchWord: str) -> bool:
        sw = list(searchWord)
        for i in range(len(searchWord)):
            c = sw[i]
            sw[i] = "*"
            word = "".join(sw)
            if self.d[word] > 1 or (word in self.d and searchWord not in self.s):
                return True
            sw[i] = c
        return False


# 202 ms 击败 31.07%
class Node:

    def __init__(self) -> None:
        self.chars = [None] * 26
        self.end = False


class DictionaryTree:

    def __init__(self) -> None:
        self.root = Node()

    def add(self, word: str):
        node = self.root
        for w in word:
            i = ord(w) - ord("a")
            if node.chars[i] == None:
                node.chars[i] = Node()
            node = node.chars[i]
        node.end = True

    def search(self, word):
        return self.search_change1(self.root, word, 0, 0)

    def search_change1(self, node, word, index, change):
        if index == len(word):
            return change == 1 and node.end
        c = ord(word[index]) - ord("a")
        if node.chars[c] is not None and self.search_change1(
            node.chars[c], word, index + 1, change
        ):
            return True
        if change == 0:
            for i in range(26):
                if (
                    i != c
                    and node.chars[i] is not None
                    and self.search_change1(node.chars[i], word, index + 1, 1)
                ):
                    return True
        return False


class MagicDictionary:

    def __init__(self):
        self.dt = DictionaryTree()

    def buildDict(self, dictionary: List[str]) -> None:
        for d in dictionary:
            self.dt.add(d)

    def search(self, searchWord: str) -> bool:
        return self.dt.search(searchWord)


s = MagicDictionary()
s.buildDict(["hello", "leetcode"])
print(s.search("hello"))
